1792C - Min Max Sort - CodeForces Solution

/*
	author: akhilendra11
*/


#include<bits/stdc++.h>
using namespace std;

#define int long long int
#define endl "\n"

void solve(){
	int n; cin>>n;
	int idx[n+1];

	for(int i=1;i<=n;i++){
		int x; cin>>x;
		idx[x]=i;
	}

	int c=n/2;

	int i=idx[c]; 
	int j=idx[n-c+1];

	if(n==1){
		cout<<"0\n";
		return;
	}
	if(i>j and n%2==0){
		cout<<n/2<<"\n";
		return;
	}

	if(n%2){
		i=j=idx[c+1];
	}
	else c--;
	
	while(c>0 and idx[c]<i and idx[n-c+1]>j){
		i=idx[c];
		j=idx[n-c+1];
		c--;
	}

	cout<<c<<"\n";

}

int32_t main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

	int t; cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}